
import java.util.Arrays;
//实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
//
//如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
//必须 原地 修改，只允许使用额外常数空间。
public class 下一个排列 {
    public static void main(String[] args) {
        int[] nums={1,2,3};
        nextPermutation(nums);
    }
    public static void nextPermutation(int[] nums) {
        //从后往前，找到第一个i<i+1的值
        boolean flag=false;
        for (int i=nums.length-2; i >=0; i--) {
            if (nums[i]>=nums[i+1])
                continue;
            else{
                flag=true;
                //从后往前，找到最小的大于i的值，交换位置
                for (int j = nums.length-1; j >i ; j--) {
                    if (nums[j]<=nums[i])
                        continue;
                    else{
                        int k=nums[i];
                        nums[i]=nums[j];
                        nums[j]=k;
                        //对i后边的元素进行从小到大的排序，使用Arrays.sort排序
                        Arrays.sort(nums,i+1,nums.length);
                        break;
                    }
                }
                break;
            }
        }
        if (!flag)
            Arrays.sort(nums);
            System.out.println(Arrays.toString(nums));
    }
}
